//https://leetcode.cn/problems/accounts-merge/description/?envType=daily-question&envId=2024-07-15https://leetcode.cn/problems/accounts-merge/description/?envType=daily-question&envId=2024-07-15
class Solution {
private:
    vector<int> p;

    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        unordered_map<string, int> mp;
        vector<vector<string>> ans;
        p = vector<int> (n);

        for (int i = 0; i < n; i++) 
            p[i] = i;
        
        for (int i = 0; i < n; i++){
            for (int j = 1; j < accounts[i].size(); j++){
                auto it = mp.find(accounts[i][j]);
                if (it != mp.end())
                    p[find(i)] = find(it->second);
                else    
                    mp.insert(pair<string, int>(accounts[i][j], i));
            }
        }

        unordered_set<string> mail;
        int idx[n];
        memset(idx, -1, sizeof idx);
        for (int i = 0; i < n; i++){
            if (idx[find(i)] == -1){
                idx[find(i)] = ans.size();
                ans.push_back(vector<string>());
                ans.back().push_back(accounts[i][0]);
            }

            int pos = idx[find(i)];
            for (int j = 1; j < accounts[i].size(); j++){
                if (mail.find(accounts[i][j]) == mail.end()){
                    mail.insert(accounts[i][j]);
                    ans[pos].push_back(accounts[i][j]);
                }
            }
        }

        for (auto &x : ans)
            sort(x.begin() + 1, x.end());

        return ans;
    }
};
